package io.github.hadyang.leetcode.bytedance;

import java.util.Arrays;
import java.util.List;

/**
 * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
 *
 * <p>换句话说，第一个字符串的排列之一是第二个字符串的子串。
 *
 * <p>示例1:
 *
 * <p>输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba").
 *
 * <p>
 *
 * <p>示例2:
 *
 * <p>输入: s1= "ab" s2 = "eidboaoo" 输出: False
 *
 * <p>
 *
 * <p>注意：
 *
 * <p>输入的字符串只包含小写字母 两个字符串的长度都在 [1, 10,000] 之间
 */
public class String1016 {
  /**
   * 这道题，我们用到的算法是 <b>滑动窗口</b>
   *
   * <p>首先字符串s1的排列的可能性应该是它的长度的阶乘，因为字符串长度可能为10000，所以找出所有排列情况是不太可能。
   *
   * <p>我们可以转换思路，不要关注排列的形式，而是关注排列中元素的数量关系，
   *
   * <p>比如aab，那么，转换为数量关系就是{a:2,b:1}，因为S1长度为3，所以我们的窗口长度也为3，
   *
   * <p>如果我们在S2的找到了这样一个窗口符合出现a的次数是两个，b是一个，那么S2就是包含S1的排列的。
   *
   * @param s1
   * @param s2
   * @return
   */
  public boolean checkInclusion(String s1, String s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    int[] c1 = new int[26];
    int[] c2 = new int[26];

    for (char c : s1.toCharArray()) {
      c1[c - 'a']++;
    }

    for (int i = 0; i < len2; i++) {
      if (i >= len1) --c2[s2.charAt(i - len1) - 'a']; // 先把坐标查过的减掉
      c2[s2.charAt(i) - 'a']++;
      if (Arrays.equals(c1, c2)) return true;
    }

    return false;
  }

  /**
   * 解题思路：本题求整个字符串的全排列可以看做两步
   *
   * <p>1）首先求出所有可能出现在第一位置的字母，即begin与后面所有与它不同的字母进行交换
   *
   * <p>2）固定第一个字母，求后面字母的全排列，即递归此时begin = begin+1
   *
   * @param res
   * @param chars
   * @param firstIndex
   */
  private void permutation(List<String> res, char[] chars, int firstIndex) {
    res.add(new String(chars));

    if (firstIndex >= chars.length) {
      return;
    }

    char first = chars[firstIndex];

    for (int j = firstIndex + 1; j < chars.length; j++) {
      if (first != chars[j]) {
        chars[firstIndex] = chars[j];
        chars[j] = first;

        permutation(res, chars, firstIndex + 1);
        chars[j] = chars[firstIndex];
        chars[firstIndex] = first;
      }
    }
  }

  public static void main(String[] args) {
    String1016 main = new String1016();

    //        System.out.println(main.checkInclusion("abcdxabcde", "abcdeabcdx"));
    //        System.out.println(main.checkInclusion("ab", "eidbaooo"));
    //        System.out.println(main.checkInclusion("ab", "eidboaoo"));
    System.out.println(main.checkInclusion("food", "money"));
  }
}
